import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) return list;

            //第一个元素去重，跟前面的比较，
            //如果跟后面元素比较：会给元组内元素去重，比如（-1，-1，2）
            if (i>0 && nums[i] == nums[i-1]) continue;

            int left = i+1,right = nums.length - 1; //第二、三元素指针
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if( sum > 0) right--;
                else if(sum < 0) left++;
                else {
                    list.add(Arrays.asList(nums[i],nums[left], nums[right]));
                    //第二个元素去重
                    while (left < right && nums[left] == nums[left+1]){
                        left++;
                    }
                    //第三个元素去重
                    while (left < right && nums[right] == nums[right-1]){
                        right--;
                    }
                    //继续遍历，看后面还有下一组的（第二个数，第三个数）
                    left++;
                    right--;
                }
            }
        }
        return list;
    }
}